package com.leetcode.test.linklist;

/**
 * https://leetcode-cn.com/explore/learn/card/linked-list/193/singly-linked-list/741/
 * <p>
 * 还是有错
 */
class MyLinkedList {

    Node head;

    /**
     * Initialize your data structure here.
     */
    public MyLinkedList() {}

    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
     */
    public int get(int index) {
        Node node = getNode(index);

        if (node == null) {
            return -1;
        }

        return node.value;
    }

    private Node getNode(int index) {
        if (index < 0 || index > length()) {
            return null;
        }

        Node node = head;
        int  i    = 0;

        while (node != null && i < index) {
            node = node.next;
            i++;
        }

        return node;
    }

    /**
     * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
     */
    public void addAtHead(int val) {
        if (head == null) {
            head = new Node(val, null);
            return;
        }

        head = new Node(val, head);
    }

    /**
     * Append a node of value val to the last element of the linked list.
     */
    public void addAtTail(int val) {
        Node newTail = new Node(val, null);
        Node tail    = getNode(length() - 1);

        // 此时node就是尾部
        tail.next = newTail;
    }

    /**
     * Add a node of value val before the index-th node in the linked list.
     * If index equals to the length of linked list, the node will be appended to the end of linked list.
     * If index is greater than the length, the node will not be inserted.
     */
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > length()) {
            return;
        }

        if (index == 0) {
            if (head == null) {
                // 无头节点
                head = new Node(val, null);
            } else {
                // 新节点成头节点
                head = new Node(val, head);
            }
            return;
        }

        // index>0
        Node pre = getNode(index - 1);

        // pre已经是尾部
        if (pre.next == null) {
            pre.next = new Node(val, null);
            return;
        }

        // index插入新节点
        Node current = getNode(index);
        Node newNode = new Node(val, current);
        pre.next = newNode;
    }

    /**
     * Delete the index-th node in the linked list, if the index is valid.
     */
    public void deleteAtIndex(int index) {
        if (index < 0 || index > length()) {
            return;
        }

        Node current = getNode(index);

        if (current == head) {
            head = current.next;
            return;
        }

        Node pre = getNode(index - 1);

        pre.next = current.next;
    }

    public int length() {
        Node node   = head;
        int  length = 0;

        while (node != null) {
            length++;
            node = node.next;
        }

        return length;
    }

    static class Node {
        Node next;
        int  value;

        Node(int val, Node next) {
            this.value = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");

        Node node = head;

        while (node != null) {
            sb.append(node.value);
            node = node.next;
        }

        sb.append("]");
        return sb.toString();
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */